La modélisation par théorie des graphes consiste à abstraire les relations complexes du monde réel (comme le routage Internet ou les transitions d'état) en un objet mathématique $G = (V, E)$. En définissant les entités commesommets (Vertex) et les relations commearêtes (Edge)nous pouvons utiliser un type de données abstrait (ADT) et des algorithmes unifiés pour résoudre une grande variété de problèmes.

Définition des composants fondamentaux

• sommets (Vertex): aussi appelé nœud. Doté d'une « clé » (Key) servant d'identifiant unique, pouvant contenir un « chargement utile » (Payload).
• arêtes (Edge): relie deux sommets, indiquant qu'une relation existe entre eux. Peut être unidirectionnel (graphe orienté) ou bidirectionnel.
• poids (Weight): 边上的数值，代表成本（如距离、延迟、带宽）。

Précision mathématique

Mathématiquement, $G = (V, E)$. Où $V$ est l'ensemble des sommets et $E$ est l'ensemble des paires ordonnées $(v, w)$ formant les arêtes, avec $v, w \in V$. Cette structure hautement abstraite nous permet d'utiliser la même suite d'algorithmes BFS/DFS pour résoudre des problèmes allant de la navigation cartographique à la recommandation dans les réseaux sociaux.